Network operators and carriers are deploying packet-switched communications networks in place of circuit-switched networks. In packet-switched networks such as Internet Protocol (IP) networks, IP packets are routed according to routing state stored at each IP router in the network. Similarly, in Ethernet networks, Ethernet frames are forwarded according to forwarding state stored at each Ethernet switch in the network. The present invention applies to communications networks employing any Protocol Data Unit (PDU) based network and in this document, the terms “packet” and “packet-switched network”, “routing”, “frame” and “frame-based network”, “forwarding” and cognate terms are intended to cover any PDUs, communications networks using PDUs and the selective transmission of PDUs from network node to network node.
Multicast forwarding of data packets (where packets are sent from a source node to multiple destination nodes more or less simultaneously) is of increasing importance as demand for services such as Internet Protocol Television (IPTV) and Video on Demand (VoD) grows.
Protocols such as Intermediate System-Intermediate System (IS-IS) and Open Shortest Path First (OSPF) and Multicast OSPF are used to distribute topology information to permit distributed calculation of paths that interconnect multiple nodes, resulting in the installation of the forwarding state required to implement those paths. OSPF and IS-IS are run in a distributed manner across nodes of the network so that, for example, when a topology change occurs in the network such as a node or link failure, this information is flooded to all nodes by the protocol's operation, and each node will locally recompute paths to circumvent the failure based on a consistent view of the network topology.
In Ethernet networks, Provider Backbone Transport (PBT), also known as Provider Back-Bone Bridging-Traffic Engineering (PBB-TE), as described in Applicant's British patent number GB 2422508 is used to provide a unicast Ethernet transport technology. Provider Link State Bridging (PLSB) as described in Applicant's co-pending U.S. patent application Ser. No. 11/537,775 will be used to provide a multicast transport capability for Ethernet networks using IS-IS to set up both unicast paths and multicast trees in the network. Both above patent documents are hereby incorporated by reference.
While the present invention is not limited to the application of a routing system to Ethernet bridging, Ethernet terminology is used in this disclosure where possible. So, for example, the term filtering database (FDB) can be considered interchangeable with any term for an information repository of packet forwarding information, such as forwarding information base or label information base.
Typically, multicast trees in a PLSB network are computed using an all-pairs shortest path multicast route computation algorithm known, for example, from Applicant's co-pending U.S. Patent Application Publication No. 20070165657. In accordance with this method, when a node receives either a multicast group membership change or a network topology change (for example via a Link State Protocol Data Unit—LSP) the node employs algorithms such as Dijkstra's algorithm to compute both unicast connectivity and the set of pairs of network nodes that are connected by a shortest path which traverses the computing node. For that set of node pairs, the node determines where intersections of multicast group membership occur, and defines the required FDB entries to instantiate its portion of multicast paths accordingly. Both Unicast and Multicast forwarding state implementing the computed paths is then installed in the node's filtering database (FDB), so that received packets can be forwarded to the appropriate output port(s) of the node, based on the destination address in the frame.
As may be appreciated, identifying pairs of nodes for which the respective shortest path traverses a particular node is computationally intensive, because it involves examining the paths extending from each node to every other node. In some cases, the challenge of performing the required computations within an acceptable period of time can impose limitations on the size of the network. Clearly, more powerful processors can be used to increase the speed of computation, but only by increasing the cost of each node, which may be undesirable.
Techniques for improving the efficiency of multicast route computation in packet switched networks remain highly desirable.